#define _CRT_SECURE_NO_WARNINGS
#include<stack>
using namespace std;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

TreeNode* BuyNode(int x)
{
    TreeNode* node = new TreeNode;
    node->val = x;
    node->left = nullptr;
    node->right = nullptr;
    return node;
}
class Solution {
public:
    void PreOrder(TreeNode* root, stack<TreeNode*>& st, TreeNode* tar)
    {
        if (root == tar) return;
        st.push(root);
        if (root->left) PreOrder(root->left, st, tar);
        else
        {
            if (root->right) PreOrder(root->right, st, tar);
            else st.pop();
        }
        root = st.top();
        if (root->right) PreOrder(root->right, st, tar);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> st1, st2;
        TreeNode* cur = root;
        PreOrder(root, st1, p);
        PreOrder(root, st2, q);
        while (st1.size() != st2.size())
        {
            if (st1.size() > st2.size()) st1.pop();
            else st2.pop();
        }
        while (st1.top()->val != st2.top()->val)
        {
            st1.pop();
            st2.pop();
        }
        return st1.top();
    }
};
int main()
{
    TreeNode* tree = BuyNode(3);
    tree->left = BuyNode(5);
    tree->right = BuyNode(1);
    tree->right->left = BuyNode(0);
    tree->right->right = BuyNode(8);
    tree->left->left = BuyNode(6);
    tree->left->right = BuyNode(2);
    tree->left->right->left = BuyNode(7);
    tree->left->right->right = BuyNode(4);
    Solution().lowestCommonAncestor(tree, tree->left->right->right, tree->left->left);
    return 0;
}